/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-08-14
 * Time: 8:20
 */

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {
    }

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}
class Solution {
    public Node connect(Node root) {
        if(root==null) return null;
        Node head = root;
        while(head!=null){
            Node dummyHead = new Node(-1);
            Node dummyNext = dummyHead;
            while(head!=null){//每一层连接,左不为空就连接左,右不为空就连接右
                if(head.left!=null){
                    dummyNext.next = head.left;
                    dummyNext = dummyNext.next;
                }
                if(head.right!=null){
                    dummyNext.next = head.right;
                    dummyNext = dummyNext.next;
                }
                head = head.next;//头结点指向下一个
            }
            head = dummyHead.next;//指向下一层的头结点
        }
        return root;
    }
}

public class TestDemoo {
}
